package Algorithm.dynamicProgramming.introduct;

/**
 * 300. 最长递增子序列 https://leetcode.cn/problems/longest-increasing-subsequence
 * 题目简述：找到一个整数数组中最长递增子序列的长度。子序列为从数组中删除任意个元素而不改变剩余元素相对顺序的序列
 */
public class LengthOfLIS {

    /**
     * 思路一：动态规划
     * 1. 定义dp：dp[j]为以nums[j]结尾的最长递增子序列长度
     * 2. 状态转移方程：dp[j]即等于在nums[0]~nums[j-1]中比num[j]小的元素中的最大dp再加上1
     * 3. 初始化：dp[0] = 1;
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for(int i = 1;i < nums.length;i++) {
            int x = 0;
            for(int j = i-1;j >= 0;j--) {
                if(nums[i] > nums[j]) {
                    x = Math.max(x, dp[j]);
                }
            }
            dp[i] = x + 1;
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * 思路二：定义一个数组tails[]，其中tails[k]表示长度为k+1的子序列最小尾部元素。
     *       初始化tails[0] = nums[0];并用一个游标cur记录当前最长递增子序列尾部tails[cur]
     *       遍历当nums[]，当遇到比tails[cur]大的元素时，则最长递增子序列长度增一，
     *       当遇到比tails[cur]小的元素时，则用其替换tails中比它大的元素（tails中的元素必定是在nums[i]前面的元素）
     */
    public int lengthOfLIS2(int[] nums) {
        int[] tails = new int[nums.length];
        tails[0] = nums[0];
        int cur = 0;
        for(int i = 1;i < nums.length;i++) {
            if(nums[i] > tails[cur])
                tails[++cur] = nums[i];
            else if(nums[i] < tails[cur]) {
                int low=0, high=cur;
                while(low <= high) {
                    int mid = (low+high) / 2;
                    if(tails[mid] == nums[i])
                        break;
                    else if(tails[mid] > nums[i])
                        high = mid-1;
                    else
                        low = mid+1;
                }
                if(low > high) tails[low] = nums[i];
            }
        }
        return cur + 1;
    }
}
